package com.sxt;
/**双向列表*/
public class MyDoubleLinkedList<E> implements MyList<E> {

    /*用内部类来定义双向节点对象*/
    class Node<E> {
        E item;//记录元素
        Node<E> prev;//记录前一个节点
        Node<E> next;//记录下一个节点对象
        ///注意构造器里的参数位置  顺序
        Node(Node<E> prev,E item,Node<E> next){
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
    private Node head;//记录头节点
    private Node tail; //记录尾节点
    private int size;//记录元素个数
    //添加元素
    @Override
    public void add(E element) {
        this.linkLast(element);

    }
    /*将节点对象添加到双向链表尾部*/
    private void linkLast(E element){
        //获取尾节点
        Node t= this.tail;
        //创建新节点 注意参数的顺序 上一个的尾节点连接下一个的头节点，
        // 所以第个是和t 第二个是添加的元素 因为是尾节点所以最
        // 后一个是null
        Node<E> node=new Node<>(t,element,null );
        //将新节点为尾节点
        this.tail = node;
        //如果尾节点为空
        if(t == null){
            this.head = node;
        }else {
            //尾节点的与新节点的挂接
            t.next = node;
        }
        this.size++;
    }
    //获取元素
    @Override
    public E get(int index) {
        //检验合法性
        this.checkIndex(index);
        //根据位置查找节点对象
   Node<E> node =this.getNode(index);
        return node.item;
    }
    //检验index合法性
    private void checkIndex(int index){
        if(!(index>=0 && index<this.size )){
            throw new IndexOutOfBoundsException("Index"+index+"Size"+size);
        }
    }
    //根据位置获取指定节点对象
    private Node getNode(int index){
        //个数除以2  判断当前位置距离头或尾哪个节点更近
        //从前往后找
        if(index<(this.size >> 1)){
            //找节点时不可以移动头节点，定义多一个指针用来移动
            Node node = this.head;
            for (int i=0;i<index;i++){
                node=node.next;
            }
            return node;
            //从后往前找
        }else {
            Node node = this.tail;
            //size要减1 索引从0开始，所以size-1
            for (int i=this.size-1;i>index;i--){
                node=node.prev;
            }
            return node;
        }
    }
    //元素个数
    @Override
    public int size() {
        return this.size;
    }
    //删除元素
    @Override
    public E remove(int index) {
        //对index 进行校检
        this.checkIndex(index);
        //根据指定位置获取节点对象
        Node<E> node = this.getNode(index);
        //获取节点对象中的元素
        E item = node.item;
        //删除元素
        //判断当前节点是否为空
        if(node.prev ==null){
            //头节点
            this.head = node.next;
        }else {
            //完成当前节点的前一个节点与当前节点的后一个节点的挂接
            /*当前节点的prev 的 next(前一个节点) 等于当前节点的next*/
            node.prev.next=node.next;
        }
        //判断当前节点是否为尾节点
        if(node.next==null){
            this.tail=node.prev;

        }else {
            /*当前节点的后一个节点挂接当前节点的前一个节点*/
            //完成当前节点的直接后继节点与当前节的直接前驱节点的挂接
            //当前节点的next是下一节点的prev,下一节点的prev等当前节点的prev
            node.next.prev = node.prev;

        }
        //当前接点断掉与它直接前驱节点的连接
        node.prev=null;
        //当前接点断掉与它直接后继节点的连接  回收会快点
        node.next = null;
        node.item = null;
        this.size--;
        return item;

    }

    /*在双向链表的头添加元素*/
    public void addFirst(E element){
        this.linkFirst(element);
    }

    /*在链接的头添加元素*/
    private void linkFirst(E element) {
        //获取头对象
        Node head = this.head;
        //创建对象  node.next指向下一个节点head,所以第三个参数填head,
       //是前接点向后节点挂接
        Node node = new Node(null,element,head);
        //将新节点定义为头节点
        this.head = node;
        //判断当前链表中是否有节点，如果没有那么该节点即是头节点也是尾节点
        if (head == null){
            this.tail = node;
        }else {
            //后节点向前节点挂接
            head.prev = node;
        }
        this.size++;
    }
    //在链表的尾添加元素
    public void addLast(E element){
        this.linkLast(element);
    }
    public static void main(String[] args) {
      /*  //先接口  再是实现类
        MyList<String> myList = new MyDoubleLinkedList<>();
        myList.add("A");
        myList.add("b");
        myList.add("c");
        myList.add("d");
        System.out.println(myList.remove(0));
        System.out.println(myList.size());
        for(int i=0;i<myList.size();i++){
            System.out.println(myList.get(i));
        }*/

        /*因为上面的对象引用是接口类型定义，接口里没有addFirst与addLast方法
        * 所以下面的定义要用本身定义*/
        MyDoubleLinkedList<String> myd = new MyDoubleLinkedList<>();
        myd.add("A");
        myd.addFirst("a");
        myd.add("k");
        myd.addLast("B");
        for (int i =0;i< myd.size;i++){
            System.out.println(myd.get(i));
        }
    }
}
